/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    void split(std::string str, vector<string>& res)
    {
        string s;
        for(int i = 0; i < str.size(); i++)
        {
            if(str[i] == ',')
            {
                res.push_back(s);
                s = "";
            }
            else
                s += str[i];
        }
        res.push_back(s);

        return;
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "#";

        string str;
        queue<TreeNode*> queue;
        queue.push(root);
        str = str + std::to_string(root->val) + ",";

        while(!queue.empty())
        {
            int size = queue.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = queue.front();
                if(node->left)
                {
                    str = str + std::to_string(node->left->val) + ",";
                    queue.push(node->left);
                }
                else
                    str += "#,";

                if(node->right)
                {
                    str = str + std::to_string(node->right->val) + ",";
                    queue.push(node->right);
                }
                else
                    str += "#,";
                queue.pop();
            }
        }
            return str.substr(0, str.size()-1);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> res;
        split(data, res);

        if(res.size() == 1)
            return NULL;
        TreeNode* node = new(TreeNode);
        node->val = atoi(res[0].c_str());
        TreeNode* root = node;
        queue<TreeNode*> queue;
        queue.push(node);
        int num = 1;

        while(!queue.empty())
        {
            int size = queue.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode* cnt_node = queue.front();
                string cnt_str = res[num];
                if(res[num] == "#")
                    cnt_node->left = NULL;
                else
                {
                    TreeNode* tmp = new(TreeNode);
                    tmp->val = atoi(res[num].c_str());
                    cnt_node->left = tmp;
                    queue.push(tmp);
                }
                num++;
                if(res[num] == "#")
                    cnt_node->right = NULL;
                else
                {
                    TreeNode* tmp = new(TreeNode);
                    tmp->val = atoi(res[num].c_str());
                    cnt_node->right = tmp;
                    queue.push(tmp);
                }
                num++;
                queue.pop();
            }
        }

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));